package LC;

import java.util.ArrayList;
import java.util.List;

public class LC113 {
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            List<List<Integer>> ans = new ArrayList<>();
            dps(targetSum,root,new ArrayList<>(),ans);
            return ans;
        }
        public void dps(int target,TreeNode root,List<Integer> list,List<List<Integer>> ans){
            if(root==null){
                if(target==0){
                    ans.add(list);
                }
            }else{
                if(root.left!=null && root.left.val<=target){
                    list.add(root.left.val);
                    dps(target-root.left.val,root.left,list,ans);
                    list.remove(list.size()-1);
                }
                if(root.right!=null && root.right.val<=target){
                    list.add(root.right.val);
                    dps(target-root.right.val,root.right,list,ans);
                    list.remove(list.size()-1);
                }
            }
        }
}
